//力扣76. 最小覆盖子串
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return ""; // 如果 s 或 t 为空，或者 s 比 t 短，直接返回空字符串
        }

        int[] hash = new int[128]; // 记录 t 中每个字符的频率
        int[] hash1 = new int[128]; // 记录当前窗口内字符的频率

        // 初始化 hash
        for (char ch : t.toCharArray()) {
            hash[ch]++;
        }

        int left = 0, right = 0; // 滑动窗口的左右指针
        int count = 0; // 当前窗口内与 t 匹配的字符数量
        int minLen = Integer.MAX_VALUE; // 最小窗口的长度
        int start = 0; // 最小窗口的起始位置

        while (right < s.length()) {
            // 扩展窗口
            char ch = s.charAt(right);
            hash1[ch]++;
            if (hash[ch] > 0 && hash1[ch] <= hash[ch]) {
                count++; // 当前字符是 t 中的字符
            }
            right++;

            // 当窗口包含 t 的所有字符时，收缩窗口
            while (count == t.length()) {
                // 更新最小窗口
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                // 收缩窗口
                char leftChar = s.charAt(left);
                if (hash[leftChar] > 0 && hash1[leftChar] <= hash[leftChar]) {
                    count--; // 移除的字符是 t 中的字符
                }
                hash1[leftChar]--;
                left++;
            }
        }

        // 返回最小窗口的子串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}